package middle.code01_window_preprocess;

import lombok.extern.slf4j.Slf4j;

/**
 * 问题
 * 有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。
 * 现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将会被覆盖。
 * 目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。
 * 返回最少需要涂染几个正方形。
 * <p>
 * 如样例所示: s = RGRGR 我们涂染之后变成RRRGG满足要求了,涂染的个数为2,没有比这个更好的涂染方案
 * <p>
 * 思路（预处理）：
 * 在原始方式的处理中，计算左侧的‘G’以及右侧的‘R’的数量时，没有很好地利用前一次。
 * 因此，在优化方法中，对数组进行优化处理，使用前一次计算结果计算 左侧的‘G’以及右侧的‘R’的数量
 */
@Slf4j
public class Code04_Paint {

    private static int minPaint1(char[] arr) {
        int ans = Integer.MAX_VALUE;
        for (int cntR = 0; cntR <= arr.length; cntR++) {
            int ansTemp = 0;
            if (cntR == 0) {
                for (int i = 0; i < arr.length; i++) {
                    if (arr[i] == 'R') {
                        ansTemp++;
                    }
                }
            } else if (cntR == arr.length) {
                for (int i = 0; i < arr.length; i++) {
                    if (arr[i] == 'G') {
                        ansTemp++;
                    }
                }
            } else {
                for (int i = 0; i < cntR; i++) {
                    if (arr[i] == 'G') {
                        ansTemp++;
                    }
                }
                for (int i = cntR; i < arr.length; i++) {
                    if (arr[i] == 'R') {
                        ansTemp++;
                    }
                }
            }
            ans = Math.min(ans, ansTemp);
        }
        return ans;
    }

    private static int minPaint2(char[] arr) {
        int[] cntLeftG = new int[arr.length];
        int[] cntRightR = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 'G') {
                cntLeftG[i] = i - 1 >= 0 ? cntLeftG[i - 1] + 1 : 1;
            } else {
                cntLeftG[i] = i - 1 >= 0 ? cntLeftG[i - 1] : 0;
            }
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] == 'R') {
                cntRightR[i] = i + 1 < arr.length ? cntRightR[i + 1] + 1 : 1;
            } else {
                cntRightR[i] = i + 1 < arr.length ? cntRightR[i + 1] : 0;
            }
        }
        int ans = cntRightR[0];
        for (int i = 0; i < arr.length; i++) {
            ans = Math.min(ans, cntLeftG[i] + (i + 1 < arr.length ? cntRightR[i + 1] : 0));
        }
        return ans;
    }

    private static String[] randomString(int size) {
        String[] str = new String[size];
        for (int i = 0; i < size; i++) {
            int stringLen = (int) (Math.random() * 50) + 1;
            StringBuilder s = new StringBuilder();
            for (int j = 0; j < stringLen; j++) {
                if (Math.random() < 0.5) {
                    s.append("R");
                } else {
                    s.append("G");
                }
            }
            str[i] = s.toString();
        }
        return str;
    }


    public static void main(String[] args) {
        minPaint1("R".toCharArray());
        String[] randomStrings = randomString(100);
        for (String randomString : randomStrings) {
            int ans1 = minPaint1(randomString.toCharArray());
            int ans2 = minPaint2(randomString.toCharArray());
            if (ans1 != ans2) {
                log.error("oooooooooooooops! {}, {}, {}", randomString, ans1, ans2);
            }
            log.info("{} {}", randomString, ans1);
        }
    }
}
